package com.aug_leo.datastructure.priorityqueue;


import com.aug_leo.datastructure.queue.Queue;

/**
 * 基于<b>大顶堆</b>实现
 *
 * @param <E> 队列中元素类型, 必须实现 Priority 接口
 */
@SuppressWarnings("all")
public class PriorityQueue4<E extends Priority> implements Queue<E> {

    /**
     * 存储队列元素的数组
     */
    Priority[] array;

    /**
     * 队列中元素的数量
     */
    int size;

    public PriorityQueue4(int capacity) {
        array = new Priority[capacity];
    }

    /*
    1. 入堆新元素, 加入到数组末尾 (索引位置 child)
    2. 不断比较新加元素与它父节点(parent)优先级 (上浮)
        - 如果父节点优先级低, 则向下移动, 并找到下一个 parent
        - 直至父节点优先级更高或 child==0 为止
     */

    /**
     * 向队列尾插入值. 有的习惯命名为 enqueue
     *
     * @param offered 待插入值
     * @return 插入成功返回 true, 插入失败返回 false
     */
    @Override
    public boolean offer(E offered) {
        if (isFull()) {
            return false;
        }
        int child = size++;
        int parent = (child - 1) / 2;
        while (child > 0 && offered.priority() > array[parent].priority()) {
            array[child] = array[parent];
            child = parent;

            parent = (child - 1) / 2;
        }
        array[child] = offered;
        return true;
    }

    /*
    1. 交换堆顶和尾部元素, 让尾部元素出队
    2. (下潜)
        - 从堆顶开始, 将父元素与两个孩子较大者交换
        - 直到父元素大于两个孩子, 或没有孩子为止
     */

    /**
     * 从对列头获取值, 并移除. 有的习惯命名为 dequeue
     *
     * @return 如果队列非空返回对头值, 否则返回 null
     */
    @Override
    public E poll() {
        if (isEmpty()) {
            return null;
        }
        swap(0, size - 1);
        size--;
        Priority e = array[size];
        array[size] = null; // help GC

        // 下潜
        down(0);

        return (E) e;
    }

    /**
     * 下潜操作，用于维持优先队列的性质
     * 比较父节点与其子节点的优先级，如果子节点的优先级大于父节点，则进行交换
     *
     * @param paraent 父节点的索引
     */
    private void down(int paraent) {
        // 计算左子节点的索引
        int left = 2 * paraent + 1;
        // 计算右子节点的索引
        int righht = left + 1;
        // 假设父元素优先级最高
        int max = paraent;

        // 如果左子节点存在且优先级高于父节点，则更新最高优先级节点
        if (left < size && array[left].priority() > array[max].priority()) {
            max = left;
        }

        // 如果右子节点存在且优先级高于父节点，则更新最高优先级节点
        if (righht < size && array[righht].priority() > array[max].priority()) {
            max = righht;
        }
        // 如果有孩子节点的优先级高于父节点，则进行交换，并继续下潜
        if (max != paraent) { // 发现有孩子比父亲大
            swap(max, paraent);
            down(max);
        }
    }

    /**
     * 交换数组中两个元素的位置
     *
     * @param i 第一个元素的索引
     * @param j 第二个元素的索引
     */
    private void swap(int i, int j) {
        Priority temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    /**
     * 从对列头获取值, 不移除
     *
     * @return 如果队列非空返回对头值, 否则返回 null
     */
    @Override
    public E peek() {
        if (isEmpty()) {
            return null;
        }
        return (E) array[0];
    }

    /**
     * 检查队列是否为空
     *
     * @return 空返回 true, 否则返回 false
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    /**
     * 检查队列是否已满
     *
     * @return 满返回 true, 否则返回 false
     */
    @Override
    public boolean isFull() {
        return size == array.length;
    }
}
